package lbj.cyw.dp;
/*
* Offer 19. 正则表达式
*       我们用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。
*        最后一步 : s(m)与p(n)是否匹配?
*           思考最后一步怎么来的?分情况考虑!
* */
public class Offer19isMatch {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();
        // 考虑初始化的问题, 数组大小需要定义为m+1,n+1
        boolean[][] dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=0;i<=m;i++){
            //dp[0][0]已经初始化了 , 所以从dp[0][1]开始算起
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1)=='*'){
                    if(matches(s,p,i,j-1)){
                        dp[i][j]=dp[i-1][j] || dp[i][j-2];
                    }else{
                        dp[i][j]=dp[i][j-2];
                    }
                }else {
                    // 不为* 传入的则是j
                    if(matches(s,p,i,j)){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
            }
        }

        return dp[m][n];
    }

    // 注意j的表示, 传过来的可能是j-1也可能是j,方法里用j来表示了
    private boolean matches(String s, String p, int i, int j) {
        if(i==0){
            return false;
        }
        if(p.charAt(j-1)=='.'){
            return true;
        }
        return s.charAt(i-1)==p.charAt(j-1);
    }
}
